package sort.yht;

import sort.util.MySort;

/**
 * 功能描述：快速排序
 * @Author: yht
 * @Date: 2021/8/11 14:13
 */
public class KuaiSu implements MySort {

  @Override
  public String getName() {
    return "【快速排序】";
  }

  @Override
  public int[] sort(int[] a) {
    doSort(a, 0, a.length-1);
    return a;
  }

  static void doSort(int[] a, int oldLeft, int oldRight) {
    if(oldLeft < oldRight){
      int base = a[oldLeft], left = oldLeft, right = oldRight;
      while (left < right) {
        while (left < right && a[right] >= base){
          right--;
        }
        while (left < right && a[left] <= base){
          left++;
        }
        if(left < right){
          int m = a[right];
          a[right] = a[left];
          a[left] = m;
        }
      }
      a[oldLeft] = a[left];
      a[left] = base;
      //分别对左右边的数组部分做快速排序
      doSort(a, oldLeft, left-1);
      doSort(a, left+1, oldRight);
    }
  }

  public static void main(String[] args) {
    KuaiSu kuai = new KuaiSu();
//    int[] a = {12,43,1,53,23,3,4,9};
//    kuai.sort(a);
//    System.out.println();
    kuai.testAll();
  }
}
